#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int getKthMagicNumber(int k)
    {
        vector<int> df(k + 1);
        df[1] = 1;
        int dp3 = 1, dp5 = 1, dp7 = 1;
        for (int i = 2; i <= k; i++)
        {
            int number3 = df[dp3] * 3, number5 = df[dp5] * 5, number7 = df[dp7] * 7;
            df[i] = min(min(number3, number5), number7);
            if (df[i] == number3)
            {
                dp3++;
            }
            if (df[i] == number5)
            {
                dp5++;
            }
            if (df[i] == number7)
            {
                dp7++;
            }
        }
        return df[k];
    }
};

int main(int argc, char const *argv[])
{

    return 0;
}
